// Copyright 2015 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "base/trace_event/trace_buffer.h"

#include <memory>
#include <utility>
#include <vector>

#include "base/macros.h"
#include "base/trace_event/heap_profiler.h"
#include "base/trace_event/trace_event_impl.h"

namespace base {
namespace trace_event {

    namespace {

        class TraceBufferRingBuffer : public TraceBuffer {
        public:
            TraceBufferRingBuffer(size_t max_chunks)
                : max_chunks_(max_chunks)
                , recyclable_chunks_queue_(new size_t[queue_capacity()])
                , queue_head_(0)
                , queue_tail_(max_chunks)
                , current_iteration_index_(0)
                , current_chunk_seq_(1)
            {
                chunks_.reserve(max_chunks);
                for (size_t i = 0; i < max_chunks; ++i)
                    recyclable_chunks_queue_[i] = i;
            }

            std::unique_ptr<TraceBufferChunk> GetChunk(size_t* index) override
            {
                HEAP_PROFILER_SCOPED_IGNORE;

                // Because the number of threads is much less than the number of chunks,
                // the queue should never be empty.
                DCHECK(!QueueIsEmpty());

                *index = recyclable_chunks_queue_[queue_head_];
                queue_head_ = NextQueueIndex(queue_head_);
                current_iteration_index_ = queue_head_;

                if (*index >= chunks_.size())
                    chunks_.resize(*index + 1);

                TraceBufferChunk* chunk = chunks_[*index].release();
                chunks_[*index] = NULL; // Put NULL in the slot of a in-flight chunk.
                if (chunk)
                    chunk->Reset(current_chunk_seq_++);
                else
                    chunk = new TraceBufferChunk(current_chunk_seq_++);

                return std::unique_ptr<TraceBufferChunk>(chunk);
            }

            void ReturnChunk(size_t index,
                std::unique_ptr<TraceBufferChunk> chunk) override
            {
                // When this method is called, the queue should not be full because it
                // can contain all chunks including the one to be returned.
                DCHECK(!QueueIsFull());
                DCHECK(chunk);
                DCHECK_LT(index, chunks_.size());
                DCHECK(!chunks_[index]);
                chunks_[index] = std::move(chunk);
                recyclable_chunks_queue_[queue_tail_] = index;
                queue_tail_ = NextQueueIndex(queue_tail_);
            }

            bool IsFull() const override { return false; }

            size_t Size() const override
            {
                // This is approximate because not all of the chunks are full.
                return chunks_.size() * TraceBufferChunk::kTraceBufferChunkSize;
            }

            size_t Capacity() const override
            {
                return max_chunks_ * TraceBufferChunk::kTraceBufferChunkSize;
            }

            TraceEvent* GetEventByHandle(TraceEventHandle handle) override
            {
                if (handle.chunk_index >= chunks_.size())
                    return NULL;
                TraceBufferChunk* chunk = chunks_[handle.chunk_index].get();
                if (!chunk || chunk->seq() != handle.chunk_seq)
                    return NULL;
                return chunk->GetEventAt(handle.event_index);
            }

            const TraceBufferChunk* NextChunk() override
            {
                if (chunks_.empty())
                    return NULL;

                while (current_iteration_index_ != queue_tail_) {
                    size_t chunk_index = recyclable_chunks_queue_[current_iteration_index_];
                    current_iteration_index_ = NextQueueIndex(current_iteration_index_);
                    if (chunk_index >= chunks_.size()) // Skip uninitialized chunks.
                        continue;
                    DCHECK(chunks_[chunk_index]);
                    return chunks_[chunk_index].get();
                }
                return NULL;
            }

            void EstimateTraceMemoryOverhead(
                TraceEventMemoryOverhead* overhead) override
            {
                overhead->Add("TraceBufferRingBuffer", sizeof(*this));
                for (size_t queue_index = queue_head_; queue_index != queue_tail_;
                     queue_index = NextQueueIndex(queue_index)) {
                    size_t chunk_index = recyclable_chunks_queue_[queue_index];
                    if (chunk_index >= chunks_.size()) // Skip uninitialized chunks.
                        continue;
                    chunks_[chunk_index]->EstimateTraceMemoryOverhead(overhead);
                }
            }

        private:
            bool QueueIsEmpty() const { return queue_head_ == queue_tail_; }

            size_t QueueSize() const
            {
                return queue_tail_ > queue_head_
                    ? queue_tail_ - queue_head_
                    : queue_tail_ + queue_capacity() - queue_head_;
            }

            bool QueueIsFull() const { return QueueSize() == queue_capacity() - 1; }

            size_t queue_capacity() const
            {
                // One extra space to help distinguish full state and empty state.
                return max_chunks_ + 1;
            }

            size_t NextQueueIndex(size_t index) const
            {
                index++;
                if (index >= queue_capacity())
                    index = 0;
                return index;
            }

            size_t max_chunks_;
            std::vector<std::unique_ptr<TraceBufferChunk>> chunks_;

            std::unique_ptr<size_t[]> recyclable_chunks_queue_;
            size_t queue_head_;
            size_t queue_tail_;

            size_t current_iteration_index_;
            uint32_t current_chunk_seq_;

            DISALLOW_COPY_AND_ASSIGN(TraceBufferRingBuffer);
        };

        class TraceBufferVector : public TraceBuffer {
        public:
            TraceBufferVector(size_t max_chunks)
                : in_flight_chunk_count_(0)
                , current_iteration_index_(0)
                , max_chunks_(max_chunks)
            {
                chunks_.reserve(max_chunks_);
            }

            std::unique_ptr<TraceBufferChunk> GetChunk(size_t* index) override
            {
                HEAP_PROFILER_SCOPED_IGNORE;

                // This function may be called when adding normal events or indirectly from
                // AddMetadataEventsWhileLocked(). We can not DECHECK(!IsFull()) because we
                // have to add the metadata events and flush thread-local buffers even if
                // the buffer is full.
                *index = chunks_.size();
                chunks_.push_back(NULL); // Put NULL in the slot of a in-flight chunk.
                ++in_flight_chunk_count_;
                // + 1 because zero chunk_seq is not allowed.
                return std::unique_ptr<TraceBufferChunk>(
                    new TraceBufferChunk(static_cast<uint32_t>(*index) + 1));
            }

            void ReturnChunk(size_t index,
                std::unique_ptr<TraceBufferChunk> chunk) override
            {
                DCHECK_GT(in_flight_chunk_count_, 0u);
                DCHECK_LT(index, chunks_.size());
                DCHECK(!chunks_[index]);
                --in_flight_chunk_count_;
                chunks_[index] = chunk.release();
            }

            bool IsFull() const override { return chunks_.size() >= max_chunks_; }

            size_t Size() const override
            {
                // This is approximate because not all of the chunks are full.
                return chunks_.size() * TraceBufferChunk::kTraceBufferChunkSize;
            }

            size_t Capacity() const override
            {
                return max_chunks_ * TraceBufferChunk::kTraceBufferChunkSize;
            }

            TraceEvent* GetEventByHandle(TraceEventHandle handle) override
            {
                if (handle.chunk_index >= chunks_.size())
                    return NULL;
                TraceBufferChunk* chunk = chunks_[handle.chunk_index];
                if (!chunk || chunk->seq() != handle.chunk_seq)
                    return NULL;
                return chunk->GetEventAt(handle.event_index);
            }

            const TraceBufferChunk* NextChunk() override
            {
                while (current_iteration_index_ < chunks_.size()) {
                    // Skip in-flight chunks.
                    const TraceBufferChunk* chunk = chunks_[current_iteration_index_++];
                    if (chunk)
                        return chunk;
                }
                return NULL;
            }

            void EstimateTraceMemoryOverhead(
                TraceEventMemoryOverhead* overhead) override
            {
                const size_t chunks_ptr_vector_allocated_size = sizeof(*this) + max_chunks_ * sizeof(decltype(chunks_)::value_type);
                const size_t chunks_ptr_vector_resident_size = sizeof(*this) + chunks_.size() * sizeof(decltype(chunks_)::value_type);
                overhead->Add("TraceBufferVector", chunks_ptr_vector_allocated_size,
                    chunks_ptr_vector_resident_size);
                for (size_t i = 0; i < chunks_.size(); ++i) {
                    TraceBufferChunk* chunk = chunks_[i];
                    // Skip the in-flight (nullptr) chunks. They will be accounted by the
                    // per-thread-local dumpers, see ThreadLocalEventBuffer::OnMemoryDump.
                    if (chunk)
                        chunk->EstimateTraceMemoryOverhead(overhead);
                }
            }

        private:
            size_t in_flight_chunk_count_;
            size_t current_iteration_index_;
            size_t max_chunks_;
            ScopedVector<TraceBufferChunk> chunks_;

            DISALLOW_COPY_AND_ASSIGN(TraceBufferVector);
        };

    } // namespace

    TraceBufferChunk::TraceBufferChunk(uint32_t seq)
        : next_free_(0)
        , seq_(seq)
    {
    }

    TraceBufferChunk::~TraceBufferChunk() { }

    void TraceBufferChunk::Reset(uint32_t new_seq)
    {
        for (size_t i = 0; i < next_free_; ++i)
            chunk_[i].Reset();
        next_free_ = 0;
        seq_ = new_seq;
        cached_overhead_estimate_.reset();
    }

    TraceEvent* TraceBufferChunk::AddTraceEvent(size_t* event_index)
    {
        DCHECK(!IsFull());
        *event_index = next_free_++;
        return &chunk_[*event_index];
    }

    void TraceBufferChunk::EstimateTraceMemoryOverhead(
        TraceEventMemoryOverhead* overhead)
    {
        if (!cached_overhead_estimate_) {
            cached_overhead_estimate_.reset(new TraceEventMemoryOverhead);

            // When estimating the size of TraceBufferChunk, exclude the array of trace
            // events, as they are computed individually below.
            cached_overhead_estimate_->Add("TraceBufferChunk",
                sizeof(*this) - sizeof(chunk_));
        }

        const size_t num_cached_estimated_events = cached_overhead_estimate_->GetCount("TraceEvent");
        DCHECK_LE(num_cached_estimated_events, size());

        if (IsFull() && num_cached_estimated_events == size()) {
            overhead->Update(*cached_overhead_estimate_);
            return;
        }

        for (size_t i = num_cached_estimated_events; i < size(); ++i)
            chunk_[i].EstimateTraceMemoryOverhead(cached_overhead_estimate_.get());

        if (IsFull()) {
            cached_overhead_estimate_->AddSelf();
        } else {
            // The unused TraceEvents in |chunks_| are not cached. They will keep
            // changing as new TraceEvents are added to this chunk, so they are
            // computed on the fly.
            const size_t num_unused_trace_events = capacity() - size();
            overhead->Add("TraceEvent (unused)",
                num_unused_trace_events * sizeof(TraceEvent));
        }

        overhead->Update(*cached_overhead_estimate_);
    }

    TraceResultBuffer::OutputCallback
    TraceResultBuffer::SimpleOutput::GetCallback()
    {
        return Bind(&SimpleOutput::Append, Unretained(this));
    }

    void TraceResultBuffer::SimpleOutput::Append(
        const std::string& json_trace_output)
    {
        json_output += json_trace_output;
    }

    TraceResultBuffer::TraceResultBuffer()
        : append_comma_(false)
    {
    }

    TraceResultBuffer::~TraceResultBuffer() { }

    void TraceResultBuffer::SetOutputCallback(
        const OutputCallback& json_chunk_callback)
    {
        output_callback_ = json_chunk_callback;
    }

    void TraceResultBuffer::Start()
    {
        append_comma_ = false;
        output_callback_.Run("[");
    }

    void TraceResultBuffer::AddFragment(const std::string& trace_fragment)
    {
        if (append_comma_)
            output_callback_.Run(",");
        append_comma_ = true;
        output_callback_.Run(trace_fragment);
    }

    void TraceResultBuffer::Finish()
    {
        output_callback_.Run("]");
    }

    TraceBuffer* TraceBuffer::CreateTraceBufferRingBuffer(size_t max_chunks)
    {
        return new TraceBufferRingBuffer(max_chunks);
    }

    TraceBuffer* TraceBuffer::CreateTraceBufferVectorOfSize(size_t max_chunks)
    {
        return new TraceBufferVector(max_chunks);
    }

} // namespace trace_event
} // namespace base
